#include <vector>
#include <assert.h>

using namespace std;

#define SIZEOF_ARRAY(x) ((sizeof(x))/(sizeof(x[0])))
#define A2V(x)  array2vector(x, SIZEOF_ARRAY(x))

typedef unsigned __int64 ulong;
typedef vector<ulong> vector_int;
const ulong mask = 0x100000000;

void verify_multi(const vector_int& l, const vector_int& r, const vector_int& ret);
void verify_mod(const vector_int& l, const vector_int& r, const vector_int& mod, const vector_int& div);
#if 0
#define VERIFY_MULTI(A, B, C)	verify_multi(A, B, C)
#define VERIFY_MOD(A, B, C, D)	verify_mod(A, B, C, D)
#else
#define VERIFY_MULTI(A, B, C)
#define VERIFY_MOD(A, B, C, D)
#endif

vector_int calc_rsa_3(const vector_int& n, vector_int e, vector_int input);
void dump_hex(const vector_int& v);

// common, low complex functions
inline void adjust(vector_int& v)
{
	ulong carray = 0;
	for (int i = 0; i < v.size(); i++)
	{
		if (carray != 0 || v[i] >= mask)
		{
			carray += v[i];
			v[i] = carray % mask;
			carray = carray / mask;
		}
	}
	if (carray > 0)
		v.push_back(carray);
}

inline void clear_leading_zero(vector_int& v)
{
	for (int i = v.size() - 1; i > 0; i--) // remain the last "0"
	{
		if (v[i] != 0)
			break;
		v.pop_back();
	}
}

inline vector_int operator+(const vector_int& l, const vector_int& r)
{
	int max = l.size() > r.size() ? l.size() : r.size();
	vector_int ret(max, 0);
	for (int i = 0; i < max; i++)
	{
		ret[i] = (i < l.size() ? l[i] : 0) + (i < r.size() ? r[i] : 0);
	}
	adjust(ret);
	return ret;
}

inline vector_int operator-(const vector_int& l, const vector_int& r)
{
	assert(l.size() >= r.size());
	ulong carray = 0;
	vector_int ret(l);
	for (int i = 0; i < r.size() || carray != 0; i++)
	{
		ulong rv = (i < r.size() ? r[i] : 0);
		if (l[i] < (rv + carray))
		{
			ret[i] += mask - rv - carray;
			carray = 1;
		}
		else
		{
			ret[i] -= rv + carray;
			carray = 0;
		}
	}
	assert(carray == 0);
	clear_leading_zero(ret);
	return ret;
}

inline bool operator>(const vector_int& l, const vector_int& r)
{
	if (l.size() > r.size())
		return true;
	else if (l.size() < r.size())
		return false;
	else
	{
		for (int i = l.size() - 1; i >= 0; i--)
		{
			if (l[i] < r[i])
				return false;
			else if (l[i] > r[i])
				return true;
		}
		return false;
	}
}

inline bool operator>=(const vector_int& l, const vector_int& r)
{
	return !(r > l);
}

inline bool operator==(const vector_int& l, const vector_int& r)
{
	if (l.size() != r.size())
		return false;

	for (int i = 0; i < l.size(); i++)
	{
		if (l[i] != r[i])
			return false;
	}
	return true;
}

inline bool bit_value(const vector_int& v, int bit)
{
	int idx = bit / 32;
	bit %= 32;
	return (v[idx] >> bit) & 1;
}

//complex function
vector_int operator%(const vector_int& l, const vector_int& r);
